﻿//Author:Michal Sporna
//License: https://operationsneakpeek.codeplex.com/license

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

namespace World
{
    /// <summary>
    /// Class that handles pathfinding
    /// </summary>
    public static class PathFinding
    {
        #region properties
        //public static List<Node> Nodes { get; set; }
        public static List<Node> OpenList;
        public static List<Node> ClosedList;
        public static List<Node> PathNodes;
        public static bool IsPathFound;

        //costs
        public static int GRAtio;
        public static int GDiagonalRatio;
        public static int HRatio;
     
        #endregion

        #region public fields

        public static bool StartPathFinding;

        #endregion

        #region private fields
        private static Vector2 _EndPoint; //where player tapped
        private static Node _StartNode;
        private static Node _EndNode;
        private static int NumOfNodesVert;
        private static int NumOfNodesHor;
        private static int _PathNodeID;
        private static Node _ParentNode = null;
        private static bool _SearchRestartNeeded;
        private static bool _ParentNodeReached;
        private static Node _CurrentNode; //used when generating the path
        #endregion

        #region methods



        /// <summary>
        /// Init nodes-
        /// divide the map cell into rectangles
        /// </summary>
        public static void InitNodes()
        {
            //declare
            Node node = null;
            //int NumOfNodesVert = -1;
            //int NumOfNodesHor = -1;
            int X = 0;
            int Y = 0;

            try
            {
                if (WorldManager.Nodes != null)
                {
                    return;
                }

                //instantiate lists
                WorldManager.Nodes = null;
                WorldManager.Nodes = new List<Node>();
               

                OpenList = new List<Node>();
                ClosedList = new List<Node>();
                PathNodes = null;
                IsPathFound = false; 
                
                //set ratio
                //GRAtio = 1;
                //GDiagonalRatio = 14;
                //HRatio = 10;

               

                #region divide map cell into nodes

                #region regular walkable nodes


                //determine how many nodes are there going to be horizontally
                NumOfNodesHor = (Util.Cache.GraphicsDevice.Viewport.Width + WorldManager.WorldConfig.NodeWidth) / WorldManager.WorldConfig.NodeWidth;
                NumOfNodesVert = Util.Cache.GraphicsDevice.Viewport.Height / WorldManager.WorldConfig.NodeHeight;

                //horizontal
                for (int nodeVert = 0; nodeVert < NumOfNodesVert; nodeVert++)
                {
                    //prepare all columns in that row
                    //reset X
                    X = 0;
                    for (int nodeHor = 0; nodeHor < NumOfNodesHor; nodeHor++)
                    {
                        node = new Node();
                        node.NodeType = Util.Helpers.PublicEnums.NodeType.Node;
                        node.ID = nodeHor;
                        node.Row = nodeVert;
                        node.UniqueID = nodeHor + "" + nodeVert;

                        //see if a regular node size can be fitted here
                        node.Rectangle = new Rectangle(X, Y, WorldManager.WorldConfig.NodeWidth, WorldManager.WorldConfig.NodeHeight);

                        //do a simulation whtether or not the node is walkable
                        if (Levels.LevelManager.CurrentMap.IsFreeToGoSimulation(new int[] { node.Rectangle.X, node.Rectangle.Y, WorldManager.WorldConfig.NodeWidth, WorldManager.WorldConfig.NodeHeight}))
                        {
                            node.IsWalkable = true;
                        }
                        else
                        {
                            node.IsWalkable = false;
                        }

                        //add to the collection of nodes
                        WorldManager.Nodes.Add(node);

                        //increment X
                        X += WorldManager.WorldConfig.NodeWidth;
                    }

                    //increment Y to draw next row
                    Y += World.WorldManager.WorldConfig.NodeHeight;
                }


                #endregion




                #endregion


            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }

        }


        /// <summary>
        /// Init nodes-
        /// divide the map cell into rectangles
        /// returns list of created nodes
        /// </summary>
        public static List<Node> InitNodesWithReturn()
        {
            //declare
            Node node = null;
            List<Node> returnNodes = null;
            //int NumOfNodesVert = -1;
            //int NumOfNodesHor = -1;
            int X = 0;
            int Y = 0;

            try
            {
                //instantiate lists
                returnNodes = new List<Node>();

                #region divide map cell into nodes

                #region regular walkable nodes


                //determine how many nodes are there going to be horizontally
                NumOfNodesHor = (Util.Cache.GraphicsDevice.Viewport.Width + WorldManager.WorldConfig.NodeWidth) / WorldManager.WorldConfig.NodeWidth;
                NumOfNodesVert = Util.Cache.GraphicsDevice.Viewport.Height / WorldManager.WorldConfig.NodeHeight;

                //horizontal
                for (int nodeVert = 0; nodeVert < NumOfNodesVert; nodeVert++)
                {
                    //prepare all columns in that row
                    //reset X
                    X = 0;
                    for (int nodeHor = 0; nodeHor < NumOfNodesHor; nodeHor++)
                    {
                        node = new Node();
                        node.NodeType = Util.Helpers.PublicEnums.NodeType.Node;
                        node.ID = nodeHor;
                        node.Row = nodeVert;
                        node.UniqueID = nodeHor + "" + nodeVert;

                        //see if a regular node size can be fitted here
                        node.Rectangle = new Rectangle(X, Y, WorldManager.WorldConfig.NodeWidth, WorldManager.WorldConfig.NodeHeight);

                        //do a simulation whtether or not the node is walkable
                        if (Levels.LevelManager.CurrentMap.IsFreeToGoSimulation(new int[] { node.Rectangle.X, node.Rectangle.Y, WorldManager.WorldConfig.NodeWidth, WorldManager.WorldConfig.NodeHeight }))
                        {
                            node.IsWalkable = true;
                        }
                        else
                        {
                            node.IsWalkable = false;
                        }

                        //add to the collection of nodes
                        returnNodes.Add(node);

                        //increment X
                        X += WorldManager.WorldConfig.NodeWidth;
                    }

                    //increment Y to draw next row
                    Y += World.WorldManager.WorldConfig.NodeHeight;
                }


                #endregion




                #endregion

                return returnNodes;
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return returnNodes;
            }

        }

        /// <summary>
        /// Check which nodes are walkable
        /// and which are not
        /// (refresh)
        /// </summary>
        public static void CheckIfNodesAreWalkable()
        {
            try
            {
                for (int i = 0; i < WorldManager.Nodes.Count; i++)
                {
                    if (Levels.LevelManager.CurrentMap.IsFreeToGoSimulation(new int[] { WorldManager.Nodes[i].Rectangle.X, WorldManager.Nodes[i].Rectangle.Y, WorldManager.WorldConfig.NodeWidth, WorldManager.WorldConfig.NodeHeight }))
                    {
                        WorldManager.Nodes[i].IsWalkable = true;
                    }
                    else
                    {
                        WorldManager.Nodes[i].IsWalkable = false;
                    }
                }
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// Start looking for the best path to get to the
        /// point B (point where user tapped)
        /// </summary>
        /// <param name="endPoint"></param>
        /// <returns></returns>
        public static bool StartSearching(Vector2 endPoint)
        {
            //declare
            bool endNodeFound = false;
            bool startNodeFound = false;

            try
            {

                OpenList = new List<Node>();
                ClosedList = new List<Node>();
                PathNodes = null;
                IsPathFound = false; 

                //save endPoint
                _EndPoint = endPoint;



                //set end node
                for (int i = 0; i < WorldManager.Nodes.Count; i++)
                {

                    //end ndode
                    if (!endNodeFound)
                    {
                        if ((endPoint.X >= WorldManager.Nodes[i].Rectangle.X && endPoint.X <= WorldManager.Nodes[i].Rectangle.X + WorldManager.Nodes[i].Rectangle.Width) && (endPoint.Y >= WorldManager.Nodes[i].Rectangle.Y && endPoint.Y <= WorldManager.Nodes[i].Rectangle.Y + WorldManager.Nodes[i].Rectangle.Height))
                        {
                           

                                //found-end node
                                WorldManager.Nodes[i].IsWalkable = true;
                                WorldManager.Nodes[i].IsEndPoint = true;

                                endNodeFound = true;

                                //save end node
                                _EndNode = WorldManager.Nodes[i];
                            
                        }
                    }

                    //start node?
                    if (!startNodeFound)
                    {
                        //if ((Util.Cache.Avatar.CurrentPosition.X + (Util.Cache.Avatar.Width / 2) >= Nodes[i].Rectangle.X && Util.Cache.Avatar.CurrentPosition.X + (Util.Cache.Avatar.Width / 2) <= Nodes[i].Rectangle.X + Nodes[i].Rectangle.Width) && (Util.Cache.Avatar.CurrentPosition.Y + (Util.Cache.Avatar.Height / 2) >= Nodes[i].Rectangle.Y && Util.Cache.Avatar.CurrentPosition.Y + (Util.Cache.Avatar.Height / 2) <= Nodes[i].Rectangle.Y + Nodes[i].Rectangle.Height))
                        if ((Util.Cache.Avatar.CurrentPosition.X == WorldManager.Nodes[i].Rectangle.X) && (Util.Cache.Avatar.CurrentPosition.Y == WorldManager.Nodes[i].Rectangle.Y))
                        {
                           
                               
                            


                            //found-start node
                            WorldManager.Nodes[i].IsParent = true; //this changes when a new parent is selected
                            WorldManager.Nodes[i].IsStartNode = true;//this property does not change until end of move
                            WorldManager.Nodes[i].IsPartOfPath = true;
                            _PathNodeID += 1;
                            WorldManager.Nodes[i].PathID = _PathNodeID;
                            _StartNode = WorldManager.Nodes[i];//save start node

                            //add to the open list first
                            OpenList.Add(WorldManager.Nodes[i]);


                            startNodeFound = true;
                        }
                    }

                    //stop looking if both start and end nodes have been found
                    if (startNodeFound && endNodeFound)
                    {
                        break;
                    }


                }


                if (startNodeFound && endNodeFound)
                {
                    //reset is path found flag
                    IsPathFound = false;
                    _SearchRestartNeeded = false;

                    //get adjacent nodes of current node
                    FindAdjacentNodes();

                    //search for the path (do it as long as the target node has been found)
                    SearchForThePath();

                    //generate the path based on
                    GeneratePath();

                    return true;
                }
                else
                {
                    return false;
                }
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// Start looking for the best path to get to the
        /// point B (point where user tapped)
        /// </summary>
        /// <param name="endPoint"></param>
        /// <returns></returns>
        public static bool StartSearching(Rectangle startPointRect,Vector2 endPoint)
        {
            //declare
            bool endNodeFound = false;
            bool startNodeFound = false;

            try
            {
                //if end point is on avatar -meaning player tapped on avatar, cancel path searching
                //if ((_EndPoint.X > Util.Cache.Avatar.CurrentPosition.X && _EndPoint.X < Util.Cache.Avatar.CurrentPosition.X + Util.Cache.Avatar.Width) && (_EndPoint.Y > Util.Cache.Avatar.CurrentPosition.Y && _EndPoint.Y < Util.Cache.Avatar.CurrentPosition.Y + Util.Cache.Avatar.Height))
                //{
                //    return false;
                //}

                OpenList = new List<Node>();
                ClosedList = new List<Node>();
                PathNodes = null;
                IsPathFound = false; 

                //save endPoint
                _EndPoint = endPoint;



                //set end node
                for (int i = 0; i < WorldManager.Nodes.Count; i++)
                {

                    //end ndode
                    if (!endNodeFound)
                    {
                        if ((endPoint.X >= WorldManager.Nodes[i].Rectangle.X && endPoint.X <= WorldManager.Nodes[i].Rectangle.X + WorldManager.Nodes[i].Rectangle.Width) && (endPoint.Y >= WorldManager.Nodes[i].Rectangle.Y && endPoint.Y <= WorldManager.Nodes[i].Rectangle.Y + WorldManager.Nodes[i].Rectangle.Height))
                        {

                           

                                //found-end node
                                WorldManager.Nodes[i].IsWalkable = true;
                                WorldManager.Nodes[i].IsEndPoint = true;

                                endNodeFound = true;

                                //save end node
                                _EndNode = WorldManager.Nodes[i];
                            
                        }
                    }

                    //start node?
                    if (!startNodeFound)
                    {
                        if ((startPointRect.X >= WorldManager.Nodes[i].Rectangle.X && startPointRect.X + (startPointRect.Width) <= WorldManager.Nodes[i].Rectangle.X + WorldManager.Nodes[i].Rectangle.Width) && (startPointRect.Y >= WorldManager.Nodes[i].Rectangle.Y && startPointRect.Y + (startPointRect.Height) <= WorldManager.Nodes[i].Rectangle.Y + WorldManager.Nodes[i].Rectangle.Height))
                        {


                            //found-start node
                            WorldManager.Nodes[i].IsParent = true; //this changes when a new parent is selected
                            WorldManager.Nodes[i].IsStartNode = true;//this property does not change until end of move
                            WorldManager.Nodes[i].IsPartOfPath = true;
                            _PathNodeID += 1;
                            WorldManager.Nodes[i].PathID = _PathNodeID;
                            _StartNode = WorldManager.Nodes[i];//save start node

                            //add to the open list first
                            OpenList.Add(WorldManager.Nodes[i]);


                            startNodeFound = true;
                        }
                    }

                    //stop looking if both start and end nodes have been found
                    if (startNodeFound && endNodeFound)
                    {
                        break;
                    }


                }

                if (startNodeFound && endNodeFound)
                {
                    //reset is path found flag
                    IsPathFound = false;
                    _SearchRestartNeeded = false;

                    //get adjacent nodes of current node
                    FindAdjacentNodes();

                    //search for the path (do it as long as the target node has been found)
                    if (!SearchForThePath())
                    {
                        //if search for path failed,return false
                        if (Util.Cache.Avatar.IsFollowing)
                        {
                            return true;
                        }
                        else
                        {
                            return false;
                        }
                    }

                    //generate the path based on
                    GeneratePath();

                    return true;
                }
                else
                {
                    return false;
                }
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// loop thru all nodes
        /// until the path is found
        /// and the end point is reached
        /// </summary>
        public static bool SearchForThePath()
        {
            try
            {
                //loop until the target is reached
                //thru open list (only those nodes that are children of current parent)
                //select node with the highest F
                //move it to the closed list
                //set is as parent
                //findAdjacentNodes
                //and start over-loop thru the open list

                //loop until the target is reached or no more nodes on the open list
                while (!IsPathFound)
                {
                    if (OpenList.Count == 0)
                    {
                        return false; //pathfinding failed
                    }

                    

                    //thru open list (only those nodes that are children of current parent)
                    //select node with the highest F
                    if (FindLowestFNode())
                    {
                        //check if target node is already on the list (path has been found)
                        if (!_ParentNode.IsEndPoint)
                        {
                            if (_SearchRestartNeeded)
                            {
                                //restart search if restart needed because dead end reached
                                RestartSearch();
                            }

                            FindAdjacentNodes();

                        }
                        else
                        {
                            IsPathFound = true;
                            break;
                        }

                    }
                    else
                    {
                        break;
                    }
                  


                }


                return true;
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// generate the found path
        /// for avatar to follow
        /// </summary>
        public static void GeneratePath()
        {
            //declare 
            Characters.Helpers.MovePatternCheckpoint currentCheckpoint = null;
            Characters.Helpers.MovePatternCheckpoint targetCheckpoint = null;
            bool cancelPath = false;

            try
            {
                //OBSOLETE
                #region delete nodes that are on the closed list but do not lead to any other nodes

                //bool hasChildren = false;
                //List<Node> nodesToRemove = new List<Node>();

                //for (int i = 0; i < ClosedList.Count; i++)
                //{
                //    if (ClosedList[i].IsEndPoint)
                //    {
                //        continue;
                //    }

                //    hasChildren = false;

                //    foreach (Node nC in ClosedList)
                //    {
                //        if (ClosedList[i].ID == nC.ParentID && ClosedList[i].Row == nC.ParentRow)
                //        {
                //            if (IsAdjacent(ClosedList[i], nC))
                //            {
                //                hasChildren = true;
                //                break; //no need to continue the loop
                //            }
                //        }
                //    }

                //    //if we are here this node (n) has no children on the closed list
                //    //so leads nowhere
                //    //so remove
                //    if (!hasChildren)
                //    {
                //        nodesToRemove.Add(ClosedList[i]);
                //    }
                //}

                ////remove
                //if (nodesToRemove.Count > 0)
                //{
                //    foreach (Node n in nodesToRemove)
                //    {
                //        ClosedList.Remove(n);

                //    }
                //}

                #endregion

                //all nodes are not needed anymore
                //Nodes.Clear();
                //Nodes = null;


                OpenList.Clear();
                OpenList = null;
                GRAtio = -1;
                HRatio = -1;
                GDiagonalRatio = -1;
                _StartNode = null;
                //NumOfNodesHor = -1;
                //NumOfNodesVert = -1;
                _ParentNode = null;

              
                //generate a path
                _ParentNodeReached = false;
                _CurrentNode = _EndNode;
                _EndNode = null;
                _PathNodeID = -1;

                if (PathNodes == null)
                {
                    PathNodes = new List<Node>();
                }

                    //add end node to the path nodes
                    PathNodes.Add(_CurrentNode);
                

                //search for the nodes with lowest F until the star tnode is reached
                //search only among nodes from the closed list
                while (!_ParentNodeReached)
                {
                   
                        FindAdjacentNodesOnTheClosedListAndGetLowestF();
                    
                    
                }

                if (PathNodes.Count > 0 )
                {
                    //create move points for the avatar
                    if (Util.Cache.Avatar.IsFollowing)
                    {
                        //avatar is following the move pattern, so do not remove checkpoint 0 and checkpoint 1
                        //checkpoint 0(current) will be removed
                        //checkpoint 1(target) will become current
                        //and new,changed path has been generated from a target checkpoint so it is ok
                        Util.Cache.Avatar.MovePoints.Clear();
                        //clear isStartOfThePath and isendOfThePath for those nodes:
                        Util.Cache.Avatar.CurrentMoveCheckpoint.IsStartOfPath = false;
                        Util.Cache.Avatar.CurrentMoveCheckpoint.IsEndOfPath = false;
                        Util.Cache.Avatar.TargetMoveCheckpoint.IsStartOfPath = false;
                        Util.Cache.Avatar.TargetMoveCheckpoint.IsEndOfPath = false;

                        //currentMoveCheckpoint and targetMoveCheckpoint MUST NOT be null at this point
                        Util.Cache.Avatar.MovePoints.Add(Util.Cache.Avatar.CurrentMoveCheckpoint);
                        Util.Cache.Avatar.MovePoints.Add(Util.Cache.Avatar.TargetMoveCheckpoint);

                       

                    }
                    else
                    {
                        //if not following a path, then clear the list and start filling it all over again
                        Util.Cache.Avatar.MovePoints = new List<Characters.Helpers.MovePatternCheckpoint>();
                    }

                    Characters.Helpers.MovePatternCheckpoint moveCheckpoint = null;
                    PathNodes.Reverse();

                    foreach(Node n in PathNodes)
                    {
                        moveCheckpoint = new Characters.Helpers.MovePatternCheckpoint();
                        moveCheckpoint.Pos = n.Rectangle;
                        moveCheckpoint.Visible = true;
                        moveCheckpoint.FollowDirection = Util.Helpers.PublicEnums.ConvertDirectionToMovePatternDirection(n.DirectionAgainstParent);
                        moveCheckpoint.IsEndOfPath = false;
                        moveCheckpoint.IsStartOfPath = n.IsStartNode;

                        moveCheckpoint.ID = n.ID;
                        moveCheckpoint.Row = n.Row;

                        //moveCheckpoint.FollowDirection = Util.Helpers.PublicEnums.ConvertDirectionToMovePatternDirection(PathNodes[i].DirectionAgainstParent);
                        Util.Cache.Avatar.MovePoints.Add(moveCheckpoint);
                    }

                    

                    //set end of path point
                    if (Util.Cache.Avatar.MovePoints.Count > 0)
                    {
                        Util.Cache.Avatar.MovePoints[Util.Cache.Avatar.MovePoints.Count - 1].IsEndOfPath = true;

                        //if there are only 2 nodes in the list, and they are not adjacent, then end following to avoid problems
                        //verify all checkpoints
                        //for(int i=0;i<Util.Cache.Avatar.MovePoints.Count;i++)
                        //{
                        //    //if not adjacent
                        //    //end follwing
                        //    if (i < Util.Cache.Avatar.MovePoints.Count && i + 1 < Util.Cache.Avatar.MovePoints.Count)
                        //    {
                        //        //save those two
                        //        currentCheckpoint = Util.Cache.Avatar.MovePoints[0];
                        //        targetCheckpoint = Util.Cache.Avatar.MovePoints[1];

                        //        if (!AreNodesAdjacentAllNodes(new int[] { Util.Cache.Avatar.MovePoints[i].ID, Util.Cache.Avatar.MovePoints[i].Row}, new int[] { Util.Cache.Avatar.MovePoints[i + 1].ID, Util.Cache.Avatar.MovePoints[i + 1].Row}))
                        //        {
                        //            Util.Cache.Avatar.MovePoints.Clear();

                        //            //currentCheckpoint = Util.Cache.Avatar.MovePoints[i]
                        //            targetCheckpoint.IsEndOfPath = true;

                        //            Util.Cache.Avatar.MovePoints.Add(currentCheckpoint);
                        //            Util.Cache.Avatar.MovePoints.Add(targetCheckpoint);
                        //            break;
                        //        }
                        //    }
                        //    else
                        //    {
                        //        break;
                        //    }
                        //}
                    }

                   //clear path nodes
                    PathNodes.Clear();
                    PathNodes = null;

                    //reset nodes
                    foreach (Node n in WorldManager.Nodes)
                    {
                        n.ResetNode();
                    }


                }

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// Check if target node has been reached
        /// by path finding algorithm
        /// </summary>
        public static bool CheckIfEndPointReached()
        {
            try
            {
                foreach (Node n in WorldManager.Nodes)
                {
                    foreach (Node cn in ClosedList)
                    {
                        if (n.ID == cn.ID && n.Row == cn.Row && (cn.IsEndPoint))
                        {
                            //target node is on the list
                            //stop looking for path
                            IsPathFound = true;
                            return true;
                        }
                    }
                }

                return false;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// Disable current parent node
        /// another parent node was added to the open list
        /// </summary>
        public static void DisableCurrentParentNode()
        {
            try
            {
                foreach (Node n in ClosedList)
                {
                    if (n.IsParent)
                    {
                        n.IsParent = false;
                        return;
                    }


                }

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// Finds node wit biggest F in the open list
        /// moves the node to the closed list
        /// removes the node from the open list
        /// makes the node parent node
        /// </summary>
        public static bool FindLowestFNode()
        {
            //declare
            Node lowestFNode=null;

            try
            {
                //loop thru the whole open list
                //because if there are 2 nodes with the same F
                //we want to get the last with the lowest F not the first
                for (int i = 0; i < OpenList.Count;i++)
                {
                    //if (OpenList[i].IsParent)
                    //{
                    //    continue; //skip if parent
                    //}

                    //if (OpenList[i].Row != _ParentNode.Row && OpenList[i].ID != _ParentNode.ID)
                    //{
                    //    continue;//skip any nodes from open list that are not neighours of current node
                    //}

                    //check if there is  a lower f than this node's F
                   if(!IsThereLowerF(OpenList[i].F))
                   {
                       lowestFNode=OpenList[i];
                   }
                        
                }

                //if the lowest F node is not null it means that there was a node with the lowest f found
                if (lowestFNode != null)
                {
                    //if chosen node with lowest F is not adjacent to current node, then cancel current path and repath
                    //as probably a dead end has been reached
                    //if (lowestFNode.ParentUniqueID != _ParentNode.UniqueID)
                    //{
                    //    _SearchRestartNeeded = true;
                    //    return true;
                    //}


                    //this is node with the biggest F
                    //current parent node is not a parent anymore
                    DisableCurrentParentNode();

                    //make it parent node
                    lowestFNode.IsParent = true;
                    lowestFNode.IsAdjacentToCurrent = false;
                    

                 

                    return true;


                }
              

                

                return false;
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// check if specified node is
        /// adjacent to specified parent node
        /// </summary>
        /// <param name="parent"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static bool IsAdjacent(Node parent, Node n)
        {
            try
            {
                
                            #region left

                            if (n.ID == parent.ID - 1 && n.Row == parent.Row)
                            {
                                //adjacent from left
                                    return true;
                             }


                            #endregion
                            #region up

                                if (n.ID == parent.ID && n.Row == parent.Row-1)
                                {
                                    //adjacent from up
                                    return true;
                                }

                            #endregion
                            #region right

                                if (n.ID == parent.ID+1 && n.Row == parent.Row)
                                {
                                    //adjacent from right
                                    return true;
                                }

                            #endregion
                            #region down

                                if (n.ID == parent.ID && n.Row == parent.Row+1)
                                {
                                    //adjacent from right
                                    return true;
                                }
                            #endregion

                                return false;
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;

            }
        }

        /// <summary>
        /// Looks for a bigger F in the open list collection
        /// if found then return true
        /// if not found then return false-it means that the specific F is the biggest
        /// </summary>
        /// <param name="F"></param>
        /// <returns></returns>
        public static bool IsThereLowerF(float F)
        {

            try
            {
                foreach (Node n in OpenList)
                {
                    if (n.IsParent)
                    {
                        continue; //skip if parent
                    }

                    //if (n.Row != _ParentNode.Row && n.ID != _ParentNode.ID)
                    //{
                    //    continue;//skip any nodes from open list that are not neighours of current node
                    //}

                        if (n.F < F)
                        {
                            return true;
                        }
                   
                }
                    //return false if
                    //at least one node from the open list was checked if F is lower
                    return false;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return true;
            }
        }

        /// <summary>
        /// if a node is on the open list already
        /// check if going thru the current parent node
        /// the path is going to be quicker
        /// </summary>
        public static void CheckIfExistingNodeHasBetterG(Node adjacentNode,Node currentNode)
        {
            try
            {
                if (!currentNode.IsStartNode)//it is impossible that a node is already on the open list if current parent is start node(first adjacent nodes are being added)
                {
                    if (adjacentNode.G<=currentNode.G)
                    {
                        adjacentNode.IsAdjacentToCurrent = true;
                        adjacentNode.ParentRow = currentNode.Row;
                        adjacentNode.ParentID = currentNode.ID;
                        //set new direction to point new parent
                        adjacentNode.DirectionAgainstParent = DetermineDirectionAgainsParent(adjacentNode, currentNode);

                        //recalculate fgh
                        adjacentNode.G = currentNode.G;
                        CalculateH(adjacentNode, _EndPoint);
                        adjacentNode.F = adjacentNode.G + adjacentNode.H;

                        //CalculateFGH(adjacentNode, currentNode, _StartNode);

                    }
                }


            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// Determine direction of adjacent node agains parent
        ///
        /// </summary>
        /// <param name="adjacentNode"></param>
        /// <param name="parentNode"></param>
        /// <returns></returns>
        public static Util.Helpers.PublicEnums.Direction DetermineDirectionAgainsParent(Node adjacentNode, Node parentNode)
        {
            //declare
            int ID = -1;
            int row = -1;

            try
            {

             

                    #region left
 
                    ID = parentNode.ID - 1;
                    row = parentNode.Row;
                    //verify that node with specified new ID and row i on the board
                    if ((adjacentNode.Row == row && adjacentNode.ID == ID) && adjacentNode.IsWalkable)
                    {
                        return Util.Helpers.PublicEnums.Direction.Left;
                    }

                    #endregion



                    #region up
                    //row-1 and ID-1
                    //set ID and row

                    ID = parentNode.ID;
                    row = parentNode.Row + 1;
                    //verify that node with specified new ID and row i on the board
                    if ((adjacentNode.Row == row && adjacentNode.ID == ID) && adjacentNode.IsWalkable)
                    {
                        return Util.Helpers.PublicEnums.Direction.Up;
                    }

                    #endregion


                    #region right

                    ID = parentNode.ID + 1;
                    row = parentNode.Row;
                    //verify that node with specified new ID and row i on the board
                    if ((adjacentNode.Row == row && adjacentNode.ID == ID) && adjacentNode.IsWalkable)
                    {
                        return Util.Helpers.PublicEnums.Direction.Right;
                    }

                    #endregion

                    #region down

                    ID = parentNode.ID;
                    row = parentNode.Row + 1;
                    //verify that node with specified new ID and row i on the board
                    if ((adjacentNode.Row == row && adjacentNode.ID == ID) && adjacentNode.IsWalkable)
                    {
                        return Util.Helpers.PublicEnums.Direction.Down;
                    }

                    #endregion

                    return Util.Helpers.PublicEnums.Direction.None;
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return Util.Helpers.PublicEnums.Direction.None;
            }
        }


        /// <summary>
        /// find adjacent nodes of current parent node
        /// </summary>
        public static void FindAdjacentNodesOnTheClosedListAndGetLowestF()
        {

            int ID = 0;
            int row = 0;
            //bool adjacentLeftAdded = false;
            //bool adjacentRightAdded = false;
            //bool adjacentDownAdded = false;
            //bool adjacentUpAdded = false;
            List<Node> candidates = new List<Node>();
            

            try
            {

                

                        //find adjacent nodes
                        foreach(Node an in ClosedList)
                        {
                            //skip if the node is already on the path nodes
                            if (PathNodes.Contains(an))
                            {
                                continue;
                            }

                            //skip current node (n)
                            //obviously
                            if (an.UniqueID==_CurrentNode.UniqueID)
                            {
                                continue;
                            }

                            #region left

                          
                                //current row and ID-1
                                //set ID and row
                                ID = _CurrentNode.ID - 1;
                                row = _CurrentNode.Row;

                                if ((an.Row == row && an.ID == ID) && an.IsWalkable)
                                {
                                    //set direction against parent (but it will be direction against preceding node in reality)
                                    //se left here-is actually right because the node is on the left of parent but avatar
                                    //must go right to reach it
                                    an.DirectionAgainstParent = Util.Helpers.PublicEnums.ComputeOppositeDirection(Util.Helpers.PublicEnums.Direction.Left);
                                    candidates.Add(an);
                                    continue;
                                }
                            


                            #endregion
                            #region up

                        
                                //row +1 and the same ID
                                //set ID and row
                                ID = _CurrentNode.ID;
                                row = _CurrentNode.Row - 1;

                                if ((an.Row == row && an.ID == ID) && an.IsWalkable)
                                {
                                    //set direction against parent (but it will be direction against preceding node in reality)
                                    //se left here-is actually right because the node is on the left of parent but avatar
                                    //must go right to reach it
                                    an.DirectionAgainstParent = Util.Helpers.PublicEnums.ComputeOppositeDirection(Util.Helpers.PublicEnums.Direction.Up);
                                    candidates.Add(an);
                                    continue;
                                }
                            

                            #endregion
                            #region right

                                //current row and ID +1
                                //set ID and row
                                ID = _CurrentNode.ID + 1;
                                row = _CurrentNode.Row;

                                if ((an.Row == row && an.ID == ID) && an.IsWalkable)
                                {
                                    //set direction against parent (but it will be direction against preceding node in reality)
                                    //se left here-is actually right because the node is on the left of parent but avatar
                                    //must go right to reach it
                                    an.DirectionAgainstParent = Util.Helpers.PublicEnums.ComputeOppositeDirection(Util.Helpers.PublicEnums.Direction.Right);
                                    candidates.Add(an);
                                    continue;
                                }



                            


                            #endregion
                            #region down


                                //row -1 and the same ID
                                //set ID and row
                                ID = _CurrentNode.ID;
                                row = _CurrentNode.Row + 1;

                                    if ((an.Row == row && an.ID == ID) && an.IsWalkable)
                                    {
                                        //set direction against parent (but it will be direction against preceding node in reality)
                                        //se left here-is actually right because the node is on the left of parent but avatar
                                        //must go right to reach it
                                        an.DirectionAgainstParent = Util.Helpers.PublicEnums.ComputeOppositeDirection(Util.Helpers.PublicEnums.Direction.Down);
                                        candidates.Add(an);
                                        continue;
                                    }


                            #endregion

                        }



                #region get node with the lowest F

                        if (candidates.Count > 0)
                        {
                            bool foundLowerF = false;

                            foreach (Node n in candidates)
                            {
                                //reset the flag
                                foundLowerF = false;

                                foreach (Node can in candidates)
                                {
                                    if (can.G < n.G)
                                    {
                                        foundLowerF = true;
                                        continue;
                                    }


                                }

                                //if found the lowest F, save it as current
                                if (!foundLowerF)
                                {
                                    _CurrentNode = n;
                                    //set path id
                                    _PathNodeID += 1;
                                    n.PathID = _PathNodeID;
                                    //add to the path nodes
                                    PathNodes.Add(n);
                                    //remove from closed list
                                    ClosedList.Remove(n);

                                    //if start node is reached then break the loop, start following
                                    if (_CurrentNode.IsStartNode)
                                    {
                                        _ParentNodeReached = true;
                                    }

                                    break;
                                }
                            }
                        }//if candidates count > 0
                        else
                        {
                            _ParentNodeReached = true;
                        }


                #endregion






            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

       


        /// <summary>
        /// find adjacent nodes of current parent node
        /// </summary>
        public static void FindAdjacentNodes()
        {
            
            int ID=0;
            int row=0;
            bool adjacentLeftAdded = false;
            bool adjacentRightAdded = false;
            bool adjacentDownAdded = false;
            bool adjacentUpAdded = false;
            int openListCountBeforeProcessing = 0;

            try
            {
                //get parent node
                //and find adjacent nodes
                //first loop thru open list
                for (int i = 0; i < OpenList.Count; i++)
                {
                    if (OpenList[i].IsParent)
                    {
                        //set parentNode
                        _ParentNode=OpenList[i];
                        //set open list count before processing
                        //so we know if any nodes were added to the open list
                        openListCountBeforeProcessing = OpenList.Count;


                        

                        //find adjacent nodes
                        for (int i1 = 0; i1 < WorldManager.Nodes.Count; i1++)
                        {

                            //if node is on closed list already, then skip the node
                            //if (DoesClosedListContainNode(Nodes[i1].ID, Nodes[i1].Row))
                            //{
                            //    continue; //skip the node
                            //}
                            //if node is on closed list already, then skip the node
                            if (ClosedList.Contains(WorldManager.Nodes[i1]))
                            {
                                continue;
                            }

                            //skip parent node
                            //obviously
                            if (WorldManager.Nodes[i1].IsParent)
                            {
                                continue;
                            }

                            #region left

                            if (!adjacentLeftAdded)
                            {
                                //current row and ID-1
                                //set ID and row
                                ID = _ParentNode.ID - 1;
                                row = _ParentNode.Row;

                                //verify that node with specified new ID and row i on the board
                                if (NodeExist(ID, row))
                                {
                                    if ((WorldManager.Nodes[i1].Row == row && WorldManager.Nodes[i1].ID == ID) && WorldManager.Nodes[i1].IsWalkable)
                                    {
                                        //set properties
                                        WorldManager.Nodes[i1].IsAdjacentToCurrent = true;
                                        WorldManager.Nodes[i1].DirectionAgainstParent = Util.Helpers.PublicEnums.Direction.Left;
                                        WorldManager.Nodes[i1].ParentID = _ParentNode.ID;
                                        WorldManager.Nodes[i1].ParentRow = _ParentNode.Row;
                                        WorldManager.Nodes[i1].ParentUniqueID = _ParentNode.UniqueID;

                                        //add to open list if not on the open list already
                                        if (!OpenList.Contains(WorldManager.Nodes[i1]))
                                        {
                                          

                                            //calculate FGH
                                            CalculateFGH(WorldManager.Nodes[i1], _ParentNode, _StartNode);
                                            OpenList.Add(WorldManager.Nodes[i1]);
                                        }
                                        else
                                        {
                                            CheckIfExistingNodeHasBetterG(WorldManager.Nodes[i1], _ParentNode);
                                        }

                                        //processed=true
                                        adjacentLeftAdded = true;
                                    }

                                }
                            }


                            #endregion
                            #region up

                            if (!adjacentUpAdded)
                            {
                                //row +1 and the same ID
                                //set ID and row
                                ID = _ParentNode.ID;
                                row = _ParentNode.Row - 1;

                                //verify that node with specified new ID and row i on the board
                                if (NodeExist(ID, row))
                                {
                                    if ((WorldManager.Nodes[i1].Row == row && WorldManager.Nodes[i1].ID == ID) && WorldManager.Nodes[i1].IsWalkable)
                                    {
                                        //set properties
                                        WorldManager.Nodes[i1].IsAdjacentToCurrent = true;
                                        WorldManager.Nodes[i1].DirectionAgainstParent = Util.Helpers.PublicEnums.Direction.Up;
                                        WorldManager.Nodes[i1].ParentID = _ParentNode.ID;
                                        WorldManager.Nodes[i1].ParentRow = _ParentNode.Row;
                                        WorldManager.Nodes[i1].ParentUniqueID = _ParentNode.UniqueID;

                                        //add to open list if not on the open list already
                                        if (!OpenList.Contains(WorldManager.Nodes[i1]))
                                        {
                                            
                                            //calculate FGH
                                            CalculateFGH(WorldManager.Nodes[i1], _ParentNode, _StartNode);
                                            OpenList.Add(WorldManager.Nodes[i1]);
                                        }
                                        else
                                        {
                                            CheckIfExistingNodeHasBetterG(WorldManager.Nodes[i1], _ParentNode);
                                        }

                                        //processed=true
                                        adjacentUpAdded = true;
                                    }
                                }
                            }

                            #endregion
                            #region right


                            if (!adjacentRightAdded)
                            {
                                //current row and ID +1
                                //set ID and row
                                ID = _ParentNode.ID + 1;
                                row = _ParentNode.Row;

                                //verify that node with specified new ID and row i on the board
                                if (NodeExist(ID, row))
                                {
                                    if ((WorldManager.Nodes[i1].Row == row && WorldManager.Nodes[i1].ID == ID) && WorldManager.Nodes[i1].IsWalkable)
                                    {
                                        //set properties
                                        WorldManager.Nodes[i1].IsAdjacentToCurrent = true;
                                        WorldManager.Nodes[i1].DirectionAgainstParent = Util.Helpers.PublicEnums.Direction.Right;
                                        WorldManager.Nodes[i1].ParentID = _ParentNode.ID;
                                        WorldManager.Nodes[i1].ParentRow = _ParentNode.Row;
                                        WorldManager.Nodes[i1].ParentUniqueID = _ParentNode.UniqueID;

                                        //add to open list if not on the open list already
                                        if (!OpenList.Contains(WorldManager.Nodes[i1]))
                                        {
                                           

                                            //calculate FGH
                                            CalculateFGH(WorldManager.Nodes[i1], _ParentNode, _StartNode);
                                            OpenList.Add(WorldManager.Nodes[i1]);
                                        }
                                        else
                                        {
                                            CheckIfExistingNodeHasBetterG(WorldManager.Nodes[i1], _ParentNode);
                                        }

                                        //processed=true
                                        adjacentRightAdded = true;
                                    }
                                }



                            }


                            #endregion
                            #region down

                            if (!adjacentDownAdded)
                            {
                                //row -1 and the same ID
                                //set ID and row
                                ID = _ParentNode.ID;
                                row = _ParentNode.Row + 1;

                                //verify that node with specified new ID and row i on the board
                                if (NodeExist(ID, row))
                                {
                                    if ((WorldManager.Nodes[i1].Row == row && WorldManager.Nodes[i1].ID == ID) && WorldManager.Nodes[i1].IsWalkable)
                                    {
                                        //set properties
                                        WorldManager.Nodes[i1].IsAdjacentToCurrent = true;
                                        WorldManager.Nodes[i1].DirectionAgainstParent = Util.Helpers.PublicEnums.Direction.Down;
                                        WorldManager.Nodes[i1].ParentID = _ParentNode.ID;
                                        WorldManager.Nodes[i1].ParentRow = _ParentNode.Row;
                                        WorldManager.Nodes[i1].ParentUniqueID = _ParentNode.UniqueID;

                                        //add to open list if not on the open list already
                                        if (!OpenList.Contains(WorldManager.Nodes[i1]))
                                        {
                                           


                                            //calculate FGH
                                            CalculateFGH(WorldManager.Nodes[i1], _ParentNode, _StartNode);
                                            OpenList.Add(WorldManager.Nodes[i1]);
                                        }
                                        else
                                        {
                                            CheckIfExistingNodeHasBetterG(WorldManager.Nodes[i1], _ParentNode);
                                        }

                                        //processed=true
                                        adjacentDownAdded = true;
                                    }
                                }


                            }
                            #endregion




                            //if all nodes have been processed, cancel the loop
                            if (adjacentLeftAdded && adjacentDownAdded && adjacentRightAdded && adjacentUpAdded)
                            {
                                

                                break;
                            }
                           



                        }



                        #region move parent to closed list and remove from open list

                        //if (openListCountBeforeProcessing == OpenList.Count)
                        //{
                        //    _SearchRestartNeeded = true;
                        //    return;
                        //}


                        //add parent node to the closed list only if closed list does not contain the node yet
                        if (!ClosedList.Contains(_ParentNode))
                        {
                            _ParentNode.IsPartOfPath = true;
                            _PathNodeID = _PathNodeID + 1;
                            _ParentNode.PathID = _PathNodeID;
                            ClosedList.Add(_ParentNode);


                            ////remove from open list
                            //RemoveFromOpenList(_ParentNode);

                            OpenList.Remove(_ParentNode);
                        }



                        #endregion

                        //#region check if no dead end reached

                        //if (openListCountBeforeProcessing == OpenList.Count)
                        //{
                        //    //no new nodes added to the open list
                        //    //which means dead end has been hit.
                        //    //remove every node from the closed&open list and start over
                        //    //this time skipping the dead end makers
                        //    //RestartSearch();//-THIOS WILL BE CALLED IN SearchForThePath
                        //    _SearchRestartNeeded = true;
                        //    return;
                        //}

                        //if (OpenList.Count - 1 == 0)
                        //{
                        //    //dead end hit, pathfinding fialed, no more nodes to add from open list
                        //    ClosedList.Add(_ParentNode);
                        //    _SearchRestartNeeded = true;
                        //}


                        //#endregion

                        
                            break; //finish with the loop as there can be only 1 parent at the time


                    }


                }



            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// checks if specified node is
        /// on the closed list
        /// </summary>
        /// <param name="ID"></param>
        /// <param name="row"></param>
        /// <returns></returns>
        public static bool DoesClosedListContainNode(int ID, int row)
        {
            try
            {
                foreach (Node n in ClosedList)
                {
                    if (n.ID == ID && n.Row == row)
                    {
                        return true;
                    }
                }

                return false;
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// determines if node with specified ID and row
        /// has a right to exist on the gameboard\
        /// without even looping thru the nodes
        /// </summary>
        /// <param name="ID"></param>
        /// <param name="Row"></param>
        /// <returns></returns>
        public static bool NodeExist(int id, int row)
        {
            try
            {
                if (id < 0)
                {
                    return false;
                }
                if (row < 0)
                {
                    return false;
                }
                if (id > NumOfNodesHor)
                {
                    return false;
                }
                //if (id > NumOfNodesVert)
                //{
                //    ID = NumOfNodesVert;
                //}
                //if (row > NumOfNodesHor)
                //{
                //    Row = NumOfNodesHor;
                //}
                if (row > NumOfNodesVert)
                {
                    return false;
                }


                return true;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// verify that ID and Row used
        /// for determining adjacent ndoes
        /// are iwthin the gameboard
        /// </summary>
        /// <param name="id"></param>
        /// <param name="row"></param>
        /// <param name="ID"></param>
        /// <param name="Row"></param>
        public static void VerifyIDAndRowNumbers(int id, int row,out int ID,out int Row)
        {
            try
            {

                
                ID = id;
                Row = row;

                if (id < 0)
                {
                    ID = 0;
                }
                if (row < 0)
                {
                    Row = 0;
                }
                if (id > NumOfNodesHor)
                {
                    ID = NumOfNodesHor;
                }
                //if (id > NumOfNodesVert)
                //{
                //    ID = NumOfNodesVert;
                //}
                //if (row > NumOfNodesHor)
                //{
                //    Row = NumOfNodesHor;
                //}
                if (row > NumOfNodesVert)
                {
                    Row = NumOfNodesVert;
                }


            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                ID = id;
                Row = row;
                return;
            }
        }


        /// <summary>
        /// calculate F G H of the specific node
        /// </summary>
        /// <param name="n"></param>
        public static void CalculateFGH(Node adjacentNode,Node parentNode,Node startNode)
        {
            try
            {
               //calculate H
                CalculateH(adjacentNode, _EndPoint);
                //calculate G
                CalculateG(parentNode, adjacentNode);
                //calculate F
                adjacentNode.F = adjacentNode.G + adjacentNode.H;
                


            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// Calculate G
        /// distance beween parent node
        /// and each of the open nodes
        /// </summary>
        /// <param name="n"></param>
        public static void CalculateG(Node parent,Node adjacentNode)
        {

            try
            {
                //first determine if the distance between parent node and next node
                //loop thru all open nodes
                //Vector2 parentNodeVector = new Vector2(parent.Rectangle.X, parent.Rectangle.Y);
                //Vector2 adjacentNodeVector = new Vector2(adjacentNode.Rectangle.X, adjacentNode.Rectangle.Y);
                //float distance = Vector2.Distance(adjacentNodeVector,parentNodeVector);

                //GRAtio = (int)(Math.Abs(adjacentNode.Rectangle.X - (float)parent.Rectangle.X) + Math.Abs(adjacentNode.Rectangle.Y - (float)parent.Rectangle.Y));
                ////n.H *= HRatio;
                //GRAtio += (int)GetTieBreaker(adjacentNode);
                GRAtio = 10;

                if (adjacentNode.DirectionAgainstParent == Util.Helpers.PublicEnums.Direction.DiagonalLeftDown || adjacentNode.DirectionAgainstParent == Util.Helpers.PublicEnums.Direction.DiagonalLeftUp || adjacentNode.DirectionAgainstParent == Util.Helpers.PublicEnums.Direction.DiagonalRightDown || adjacentNode.DirectionAgainstParent == Util.Helpers.PublicEnums.Direction.DiagonalRightUp)
                {

                    adjacentNode.G = parent.G + GDiagonalRatio;
                }
                else
                {
                    adjacentNode.G = parent.G + GRAtio;
                    


                }

            

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// calculate H-
        /// distance from current node
        /// to the target
        /// ignoring all obstacles and everything else
        /// </summary>
        /// <param name="n"></param>
        public static void CalculateH(Node n, Vector2 endPoint)
        {

            try
            {
                
                //first determine if the distance between current node and the target
                //Vector2 currentNode = new Vector2(n.Rectangle.X, n.Rectangle.Y);
                //float distance = Vector2.Distance(endPoint, currentNode);
                //n.H = (int)distance;

                //HRatio = 1;

                ////MANHATTAN:
                //n.H = (int)(Math.Abs((_EndNode.Rectangle.X + (_EndNode.Rectangle.Width / 2)) - (float)n.Rectangle.X) + Math.Abs((_EndNode.Rectangle.Y + (_EndNode.Rectangle.Height / 2)) - (float)n.Rectangle.Y));
                n.H = (int)(Math.Abs((float)n.Rectangle.X - (_EndNode.Rectangle.X + (_EndNode.Rectangle.Width / 2))) + Math.Abs((float)n.Rectangle.Y-(_EndNode.Rectangle.Y + (_EndNode.Rectangle.Height / 2))));
                n.H += (float)GetTieBreaker(n);
                n.H *= 10f;

                //DIAGONAL:
                //n.H = Math.Max(Math.Abs(_EndNode.Rectangle.X + (_EndNode.Rectangle.Width / 2) - (float)n.Rectangle.X ), Math.Abs((_EndNode.Rectangle.Y + (_EndNode.Rectangle.Height / 2)) - (float)n.Rectangle.Y));
                //n.H += (float)GetTieBreaker(n);
                //n.H *= HRatio;


                //EUCLIDEAN
                //n.H = (float)Math.Sqrt(Math.Pow(_EndNode.Rectangle.X + (_EndNode.Rectangle.Width / 2) - (float)n.Rectangle.X,2)+ Math.Pow((_EndNode.Rectangle.Y + (_EndNode.Rectangle.Height / 2)) - (float)n.Rectangle.Y,2));
                //n.H += (float)GetTieBreaker(n);
                //n.H *= HRatio;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }


        /// <summary>
        /// calculate H-
        /// distance from current node
        /// to the target
        /// ignoring all obstacles and everything else
        /// </summary>
        /// <param name="n"></param>
        public static float CalculateH(float[] n, float[] endPoint)
        {
            //declare
            float H = -1;

            try
            {

        
                ////MANHATTAN:
                //n.H = (int)(Math.Abs((_EndNode.Rectangle.X + (_EndNode.Rectangle.Width / 2)) - (float)n.Rectangle.X) + Math.Abs((_EndNode.Rectangle.Y + (_EndNode.Rectangle.Height / 2)) - (float)n.Rectangle.Y));
                H = (int)(Math.Abs(n[0] - (endPoint[0] + (WorldManager.WorldConfig.NodeWidth/ 2))) + Math.Abs(n[1] - (endPoint[1] + (WorldManager.WorldConfig.NodeHeight / 2))));
                //H += (float)GetTieBreaker(n);
                H *= 10f;

                return H;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return -1;
            }
        }


        /// <summary>
        /// calculate H-
        /// distance from avatar node
        /// to the target
        /// ignoring all obstacles and everything else
        /// </summary>
        /// <param name="n"></param>
        public static float CalculateH(float[] endPoint)
        {
            //declare
            float H = -1;

            try
            {


                ////MANHATTAN:
                //n.H = (int)(Math.Abs((_EndNode.Rectangle.X + (_EndNode.Rectangle.Width / 2)) - (float)n.Rectangle.X) + Math.Abs((_EndNode.Rectangle.Y + (_EndNode.Rectangle.Height / 2)) - (float)n.Rectangle.Y));
                H = (int)(Math.Abs(Util.Cache.Avatar.CurrentPosition.X - (endPoint[0] + (WorldManager.WorldConfig.NodeWidth / 2))) + Math.Abs(Util.Cache.Avatar.CurrentPosition.Y - (endPoint[1] + (WorldManager.WorldConfig.NodeHeight / 2))));
                //H += (float)GetTieBreaker(n);
                H *= 10f;

                return H;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return -1;
            }
        }

        /// <summary>
        ///Make sure that there are no equal nodes
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static double GetTieBreaker(Node n)
        {
            /*
             * http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12
             */
            int dx1 = n.Rectangle.X - _EndNode.Rectangle.X,
                dy1 = n.Rectangle.Y - _EndNode.Rectangle.Y,
                dx2 = _StartNode.Rectangle.X-_EndNode.Rectangle.X,
                dy2 = _StartNode.Rectangle.Y-_EndNode.Rectangle.Y,
                cross = Math.Abs(dx1 * dy2 - dx2 * dy1);
            return cross * 0.01;
        }

        #region GET AVATAR NODE

        /// <summary>
        /// Get avatar node
        /// based on avatar position
        /// </summary>
        /// <param name="nodes"></param>
        /// <returns></returns>
        public static Node GetAvatarNode(List<Node> nodes)
        {
            try
            {
                if (nodes != null)
                {
                    foreach(Node n in nodes)
                    {
                        if (Util.Cache.Avatar.CurrentPosition.X== n.Rectangle.X && Util.Cache.Avatar.CurrentPosition.Y == n.Rectangle.Y)
                        {
                            return n;

                        }

                    }
                }

                return null;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return null;
            }
        }


        /// <summary>
        /// Get avatar node
        /// based on avatar position
        /// </summary>
        /// <param name="nodes"></param>
        /// <returns></returns>
        public static Node GetAvatarNode()
        {
            try
            {
                if (Util.Cache.Avatar.IsMoving && ScannerManager.AutoScannerON)
                {
                    return GetMovingAvatarNode();

                }
                else
                {
                    //regular process:
                    if (WorldManager.Nodes != null)
                    {
                        foreach (Node n in WorldManager.Nodes)
                        {
                            if (Util.Cache.Avatar.CurrentPosition.X == n.Rectangle.X && Util.Cache.Avatar.CurrentPosition.Y == n.Rectangle.Y)
                            {
                                return n;

                            }

                        }
                    }
                }

                return null;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return null;
            }
        }

        /// <summary>
        /// Get avatar node
        /// based on avatar position
        /// </summary>
        /// <param name="nodes"></param>
        /// <returns></returns>
        public static int[] GetAvatarNode(bool returnIntArray)
        {
            try
            {
                if (Util.Cache.Avatar.IsMoving && ScannerManager.AutoScannerON)
                {
                    return GetMovingAvatarNode(true);

                }
                else
                {
                    //regular process:
                    if (WorldManager.Nodes != null)
                    {
                        foreach (Node n in WorldManager.Nodes)
                        {
                            if (Util.Cache.Avatar.CurrentPosition.X == n.Rectangle.X && Util.Cache.Avatar.CurrentPosition.Y == n.Rectangle.Y)
                            {
                                return new int[] { n.ID, n.Row };

                            }

                        }
                    }
                }

                return null;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return null;
            }
        }

        /// <summary>
        /// Get avatar node
        /// use this method if avatar is moving
        /// </summary>
        /// <returns></returns>
        public static Node GetMovingAvatarNode()
        {
            //declare
            Rectangle avatarRect;
          

            try
            {
                if (WorldManager.Nodes != null)
                {
                   //create avatar rect
                    avatarRect = new Rectangle((int)Util.Cache.Avatar.CurrentPosition.X, (int)Util.Cache.Avatar.CurrentPosition.Y, Util.Cache.Avatar.Width, Util.Cache.Avatar.Height);

                    foreach (Node n in WorldManager.Nodes)
                    {

                        switch (Util.Cache.Avatar.CurrentState)
                        {
                            case Characters.Avatar.States.GoRight1:
                                {
                                    if (avatarRect.Right > n.Rectangle.X && avatarRect.Right <= n.Rectangle.X+n.Rectangle.Width && n.Rectangle.Y==avatarRect.Y)
                                    {
                                        return n;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoRight2:
                                {
                                     if (avatarRect.Right > n.Rectangle.X && avatarRect.Right <= n.Rectangle.X+n.Rectangle.Width && n.Rectangle.Y==avatarRect.Y)
                                    {
                                        return n;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoLeft1:
                                {
                                    if (avatarRect.Left >= n.Rectangle.X && avatarRect.Left < n.Rectangle.X + n.Rectangle.Width && n.Rectangle.Y == avatarRect.Y)
                                    {
                                        return n;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoLeft2:
                                {
                                    if (avatarRect.Left >= n.Rectangle.X && avatarRect.Left < n.Rectangle.X + n.Rectangle.Width && n.Rectangle.Y==avatarRect.Y)
                                    {
                                        return n;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoUp1:
                                {
                                    if (avatarRect.Top < n.Rectangle.Y+n.Rectangle.Width && avatarRect.Top >= n.Rectangle.Y && avatarRect.X==n.Rectangle.X)
                                    {
                                        return n;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoUp2:
                                {
                                    if (avatarRect.Top < n.Rectangle.Y + n.Rectangle.Width && avatarRect.Top >= n.Rectangle.Y && avatarRect.X == n.Rectangle.X)
                                    {
                                        return n;

                                    }
                                    break;
                                }
                            case Characters.Avatar.States.GoDown1:
                                {
                                    if (avatarRect.Bottom <= n.Rectangle.Y + n.Rectangle.Height && avatarRect.Bottom > n.Rectangle.Y && n.Rectangle.X==avatarRect.X)
                                    {
                                        return n;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoDown2:
                                {
                                    if (avatarRect.Bottom <= n.Rectangle.Y + n.Rectangle.Height && avatarRect.Bottom > n.Rectangle.Y && n.Rectangle.X == avatarRect.X)
                                    {
                                        return n;

                                    }

                                    break;
                                }
                        }


                        

                    }
                }

                return null;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return null;
            }
        }

        /// <summary>
        /// Get avatar node
        /// use this method if avatar is moving
        /// </summary>
        /// <returns></returns>
        public static int[] GetMovingAvatarNode(bool returnIntArray)
        {
            //declare
            Rectangle avatarRect;


            try
            {
                if (WorldManager.Nodes != null)
                {
                    //create avatar rect
                    avatarRect = new Rectangle((int)Util.Cache.Avatar.CurrentPosition.X, (int)Util.Cache.Avatar.CurrentPosition.Y, Util.Cache.Avatar.Width, Util.Cache.Avatar.Height);

                    foreach (Node n in WorldManager.Nodes)
                    {

                        switch (Util.Cache.Avatar.CurrentState)
                        {
                            case Characters.Avatar.States.GoRight1:
                                {
                                    if (avatarRect.Right > n.Rectangle.X && avatarRect.Right <= n.Rectangle.X + n.Rectangle.Width && n.Rectangle.Y == avatarRect.Y)
                                    {
                                        return new int[] { n.ID, n.Row };

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoRight2:
                                {
                                    if (avatarRect.Right > n.Rectangle.X && avatarRect.Right <= n.Rectangle.X + n.Rectangle.Width && n.Rectangle.Y == avatarRect.Y)
                                    {
                                        return new int[] { n.ID, n.Row };

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoLeft1:
                                {
                                    if (avatarRect.Left >= n.Rectangle.X && avatarRect.Left < n.Rectangle.X + n.Rectangle.Width && n.Rectangle.Y == avatarRect.Y)
                                    {
                                        return new int[] { n.ID, n.Row };

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoLeft2:
                                {
                                    if (avatarRect.Left >= n.Rectangle.X && avatarRect.Left < n.Rectangle.X + n.Rectangle.Width && n.Rectangle.Y == avatarRect.Y)
                                    {
                                        return new int[] { n.ID, n.Row };

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoUp1:
                                {
                                    if (avatarRect.Top < n.Rectangle.Y + n.Rectangle.Width && avatarRect.Top >= n.Rectangle.Y && avatarRect.X == n.Rectangle.X)
                                    {
                                        return new int[] { n.ID, n.Row };

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoUp2:
                                {
                                    if (avatarRect.Top < n.Rectangle.Y + n.Rectangle.Width && avatarRect.Top >= n.Rectangle.Y && avatarRect.X == n.Rectangle.X)
                                    {
                                        return new int[] { n.ID, n.Row };

                                    }
                                    break;
                                }
                            case Characters.Avatar.States.GoDown1:
                                {
                                    if (avatarRect.Bottom <= n.Rectangle.Y + n.Rectangle.Height && avatarRect.Bottom > n.Rectangle.Y && n.Rectangle.X == avatarRect.X)
                                    {
                                        return new int[] { n.ID, n.Row };

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoDown2:
                                {
                                    if (avatarRect.Bottom <= n.Rectangle.Y + n.Rectangle.Height && avatarRect.Bottom > n.Rectangle.Y && n.Rectangle.X == avatarRect.X)
                                    {
                                        return new int[] { n.ID, n.Row };

                                    }

                                    break;
                                }
                        }




                    }
                }

                return null;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return null;
            }
        }

        /// <summary>
        /// check if specified node
        /// contains avatar
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static bool IsThisNodeAvatars(Node n)
        {
            try
            {
                if (!Util.Cache.Avatar.IsMoving)
                {
                    if (Util.Cache.Avatar.CurrentPosition.X == n.Rectangle.X && Util.Cache.Avatar.CurrentPosition.Y == n.Rectangle.Y)
                    {
                        return true;

                    }
                }

                    
                

                return false;
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }


        /// <summary>
        /// check if specified node
        /// contains avatar
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static bool IsThisNodeMovingAvatars(Node n)
        {

            //declare
            Rectangle avatarRect;


            try
            {
                
                    //create avatar rect
                    avatarRect = new Rectangle((int)Util.Cache.Avatar.CurrentPosition.X, (int)Util.Cache.Avatar.CurrentPosition.Y, Util.Cache.Avatar.Width, Util.Cache.Avatar.Height);

                  

                        switch (Util.Cache.Avatar.CurrentState)
                        {
                            case Characters.Avatar.States.GoRight1:
                                {
                                    if (avatarRect.Right > n.Rectangle.X && avatarRect.Right <= n.Rectangle.X + n.Rectangle.Width)
                                    {
                                        return true;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoRight2:
                                {
                                    if (avatarRect.Right > n.Rectangle.X && avatarRect.Right <= n.Rectangle.X + n.Rectangle.Width)
                                    {
                                        return true;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoLeft1:
                                {
                                    if (avatarRect.Left >= n.Rectangle.X && avatarRect.Left < n.Rectangle.X + n.Rectangle.Width)
                                    {
                                       return true;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoLeft2:
                                {
                                    if (avatarRect.Left >= n.Rectangle.X && avatarRect.Left < n.Rectangle.X + n.Rectangle.Width)
                                    {
                                        return true;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoUp1:
                                {
                                    if (avatarRect.Top < n.Rectangle.Y + n.Rectangle.Width && avatarRect.Top >= n.Rectangle.Y)
                                    {
                                      return true;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoUp2:
                                {
                                    if (avatarRect.Top < n.Rectangle.Y + n.Rectangle.Height && avatarRect.Top >= n.Rectangle.Y)
                                    {
                                       return true;

                                    }
                                    break;
                                }
                            case Characters.Avatar.States.GoDown1:
                                {
                                    if (avatarRect.Bottom >= n.Rectangle.Y + n.Rectangle.Height && avatarRect.Bottom < n.Rectangle.Y)
                                    {
                                        return true;

                                    }

                                    break;
                                }
                            case Characters.Avatar.States.GoDown2:
                                {
                                    if (avatarRect.Bottom >= n.Rectangle.Y + n.Rectangle.Height && avatarRect.Bottom < n.Rectangle.Y)
                                    {
                                        return true;

                                    }

                                    break;
                                }
                        }




                    
                

                return false;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }

        }

        #endregion

        #region ARE NODES ADJACENT?

        /// <summary>
        /// Check if two specified nodes are adjacent
        /// </summary>
        /// <param name="parentNode"></param>
        /// <param name="node2"></param>
        /// <returns></returns>
        public static bool AreNodesAdjacent(Node parentNode, Node node2)
        {
            try
            {
                if (node2.ID == parentNode.ID - 1 && node2.Row == parentNode.Row)
                {
                    return true;
                }
                else if (node2.ID == parentNode.ID && node2.Row == parentNode.Row - 1)
                {
                    return true;
                }
                else if (node2.ID == parentNode.ID +1 && node2.Row == parentNode.Row)
                {
                    return true;
                }
                else if (node2.ID == parentNode.ID && node2.Row == parentNode.Row+1)
                {
                    return true;
                }
                else if (node2.ID == parentNode.ID + 1 && node2.Row == parentNode.Row-1)
                {
                    return true;
                }
                else if (node2.ID == parentNode.ID - 1 && node2.Row == parentNode.Row-1)
                {
                    return true;
                }
                else if (node2.ID == parentNode.ID - 1 && node2.Row == parentNode.Row+1)
                {
                    return true;
                }
                else if (node2.ID == parentNode.ID + 1 && node2.Row == parentNode.Row+1)
                {
                    return true;
                }

                return false;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// Check if two specified nodes are adjacent
        /// </summary>
        /// <param name="parentNode"></param>
        /// <param name="node2"></param>
        /// <returns></returns>
        public static bool AreNodesAdjacent(int[] parentNode, int[] node2)
        {
            try
            {

                //if avatar is moving then use AreNodesAdjacentForMoving avatar (uses different flag for difficulty)
                if (ScannerManager.ChoosingNodes && Util.Cache.Avatar.IsMoving)
                {
                    return AreNodesAdjacentForMovingAvatar(parentNode, node2);
                }

                #region difficulty 1

                if (WorldManager.WorldConfig.ScannerDifficulty == 1)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 2


                if (WorldManager.WorldConfig.ScannerDifficulty == 2)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//right:
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }

                }



                #endregion

                #region difficulty 3

                if (WorldManager.WorldConfig.ScannerDifficulty == 3)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 4

                if (WorldManager.WorldConfig.ScannerDifficulty == 4)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 5

                if (WorldManager.WorldConfig.ScannerDifficulty == 5)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//5: up right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 6

                if (WorldManager.WorldConfig.ScannerDifficulty == 6)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//5: up right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//6: up left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 7

                if (WorldManager.WorldConfig.ScannerDifficulty == 7)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//5: up right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//6: up left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//7: down left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 8

                if (WorldManager.WorldConfig.ScannerDifficulty == 8)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//5: up right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//6: up left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//7: down left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//8: down right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] + 1)
                    {
                        return true;
                    }
                }
                #endregion



                return false;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }


        /// <summary>
        /// Check if two specified nodes are adjacent
        /// </summary>
        /// <param name="parentNode"></param>
        /// <param name="node2"></param>
        /// <returns></returns>
        public static bool AreNodesAdjacentAllNodes(int[] parentNode, int[] node2)
        {
            try
            {


                //1: left:
                if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                {
                    return true;

                } //2: //up
                else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                {
                    return true;

                }//3: right
                else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                {
                    return true;

                }//4: down
                else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                {
                    return true;

                }//5: up right
                else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                {
                    return true;

                }//6: up left
                else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] - 1)
                {
                    return true;

                }//7: down left
                else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] + 1)
                {
                    return true;

                }//8: down right
                else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] + 1)
                {
                    return true;
                }

                return false;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }
        /// <summary>
        /// Check if two specified nodes are adjacent
        /// </summary>
        /// <param name="parentNode"></param>
        /// <param name="node2"></param>
        /// <returns></returns>
        public static bool AreNodesAdjacentForMovingAvatar(int[] parentNode, int[] node2)
        {
            try
            {
                #region difficulty 1

                if (WorldManager.WorldConfig.AutoScannerDifficulty == 1)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 2


                if (WorldManager.WorldConfig.AutoScannerDifficulty == 2)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//right:
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }

                }

               

                #endregion

                #region difficulty 3

                if (WorldManager.WorldConfig.AutoScannerDifficulty == 3)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 4

                if (WorldManager.WorldConfig.AutoScannerDifficulty == 4)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 5

                if (WorldManager.WorldConfig.AutoScannerDifficulty == 5)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//5: up right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 6

                if (WorldManager.WorldConfig.AutoScannerDifficulty == 6)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//5: up right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//6: up left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 7

                if (WorldManager.WorldConfig.AutoScannerDifficulty == 7)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//5: up right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//6: up left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//7: down left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }

                }

                #endregion

                #region difficulty 8

                if (WorldManager.WorldConfig.AutoScannerDifficulty == 8)
                {

                    //1: left:
                    if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    } //2: //up
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//3: right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1])
                    {
                        return true;

                    }//4: down
                    else if (node2[0] == parentNode[0] && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//5: up right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//6: up left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] - 1)
                    {
                        return true;

                    }//7: down left
                    else if (node2[0] == parentNode[0] - 1 && node2[1] == parentNode[1] + 1)
                    {
                        return true;

                    }//8: down right
                    else if (node2[0] == parentNode[0] + 1 && node2[1] == parentNode[1] + 1)
                    {
                        return true;
                    }
                }
                #endregion

              

                return false;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        #endregion

        /// <summary>
        /// remove node from open list
        /// </summary>
        /// <param name="node"></param>
        public static void RemoveFromOpenList(Node node)
        {
            try
            {
                for (int i = 0; i < OpenList.Count; i++)
                {
                    if (node.Row == OpenList[i].Row && node.ID == OpenList[i].ID)
                    {
                        //remove
                        OpenList.RemoveAt(i);
                        return;
                    }
                }

            

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// check if open list
        /// contains the specified node
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public static bool DoesOpenListContainNode(Node node)
        {
            try
            {
                for (int i = 0; i < OpenList.Count; i++)
                {
                    if (OpenList[i].IsParent)
                    {
                        continue;
                    }

                    if (node.Row == OpenList[i].Row && node.ID == OpenList[i].ID)
                    {
                        return true;
                    }
                }

                return false;

            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return false;
            }
        }

        /// <summary>
        /// draw nodes
        /// for debugging purposes
        /// </summary>
        public static void DrawNodes()
        {
            try
            {
                //if (Nodes != null)
                //{
                //    //draw nodes
                //    for (int i = 0; i < Nodes.Count; i++)
                //    {
                //        if (Nodes[i].IsWalkable)
                //        {
                //            Util.Cache.Draw(Util.Cache.GetTexture("EmptyRect2").Text2D, Nodes[i].Rectangle, Color.White);
                //        }
                //        else
                //        {
                //            Util.Cache.Draw(Util.Cache.GetTexture("yellowRect").Text2D, Nodes[i].Rectangle, Color.White);
                //        }
                //    }
                   

                //}

                //if (ClosedList!= null)
                //{
                //    //draw closed nodes(ones that are part of found path)
                //    for (int i2 = 0; i2 < ClosedList.Count; i2++)
                //    {
                //        Util.Cache.Draw(Util.Cache.GetTexture("redRect").Text2D, ClosedList[i2].Rectangle, Color.White);

                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, ClosedList[i2].Row.ToString() + ClosedList[i2].ID.ToString(), new Vector2(ClosedList[i2].Rectangle.X, ClosedList[i2].Rectangle.Y), 3, Color.Black);
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, ClosedList[i2].ParentRow.ToString() + ClosedList[i2].ParentID.ToString(), new Vector2(PathNodes[i2].Rectangle.X, ClosedList[i2].Rectangle.Y + 10), 5, Color.Black);
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, ClosedList[i2].F.ToString(), new Vector2(ClosedList[i2].Rectangle.X, ClosedList[i2].Rectangle.Y + 20), 5, Color.Black);
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, ClosedList[i2].G.ToString(), new Vector2(ClosedList[i2].Rectangle.X, ClosedList[i2].Rectangle.Y + 30), 5, Color.Black);
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, ClosedList[i2].H.ToString(), new Vector2(ClosedList[i2].Rectangle.X, ClosedList[i2].Rectangle.Y + 40), 5, Color.Black);

                //    }
                //}


                if (PathNodes != null)
                {
                    //draw closed nodes(ones that are part of found path)
                    for (int i2 = 0; i2 < PathNodes.Count; i2++)
                    {
                        Util.Cache.Draw(Util.Cache.GetTexture("redRect").Text2D, PathNodes[i2].Rectangle, Color.White);

                        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, PathNodes[i2].Row.ToString() + PathNodes[i2].ID.ToString(), new Vector2(PathNodes[i2].Rectangle.X, PathNodes[i2].Rectangle.Y), 3, Color.Black);
                        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, PathNodes[i2].ParentRow.ToString() + PathNodes[i2].ParentID.ToString(), new Vector2(PathNodes[i2].Rectangle.X, PathNodes[i2].Rectangle.Y + 10), 5, Color.Black);
                        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, PathNodes[i2].F.ToString(), new Vector2(PathNodes[i2].Rectangle.X, PathNodes[i2].Rectangle.Y + 20), 5, Color.Black);
                        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, PathNodes[i2].G.ToString(), new Vector2(PathNodes[i2].Rectangle.X, PathNodes[i2].Rectangle.Y + 30), 5, Color.Black);
                        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, PathNodes[i2].H.ToString(), new Vector2(PathNodes[i2].Rectangle.X, PathNodes[i2].Rectangle.Y + 40), 5, Color.Black);

                    }
                }


                //if (Nodes != null)
                //{
                //    //draw nodes
                //    for (int i = 0; i < Nodes.Count; i++)
                //    {
                       
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, Nodes[i].Row.ToString() + Nodes[i].ID.ToString(), new Vector2(Nodes[i].Rectangle.X, Nodes[i].Rectangle.Y), 3, Color.Black);
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, Nodes[i].ParentRow.ToString() + Nodes[i].ParentID.ToString(), new Vector2(Nodes[i].Rectangle.X, Nodes[i].Rectangle.Y+10), 5, Color.Black);
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, Nodes[i].F.ToString(), new Vector2(Nodes[i].Rectangle.X, Nodes[i].Rectangle.Y + 20), 5, Color.Black);
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, Nodes[i].G.ToString(), new Vector2(Nodes[i].Rectangle.X, Nodes[i].Rectangle.Y + 30), 5, Color.Black);
                //        Util.Cache.DrawString(Util.Cache.GetFont("small").FontFace, Nodes[i].H.ToString(), new Vector2(Nodes[i].Rectangle.X, Nodes[i].Rectangle.Y + 40), 5, Color.Black);
            
                //    }

                //}
            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// restart search
        /// by clearing open&closed list
        /// except for the start node
        /// </summary>
        public static void RestartSearch()
        {
            try
            {
                //clear the lists
                OpenList.Clear();
                

                //mark all nodes(except for the start node) as dead end makers to never use them again
                foreach (Node n in ClosedList)
                {
                    if (!n.IsStartNode)
                    {
                        n.DeadEndMaker = true;
                        n.IsWalkable = false;//THIS IS THE MOST IMPORTANT
                        n.IsAdjacentToCurrent = false;
                        n.IsPartOfPath = false;
                        n.ParentID = -1;
                        n.ParentRow = -1;
                        n.PathID = -1;
                        n.F = 0;
                        n.G = 0;
                        n.H = 0;
                    }
                }

                //clear closed list
                ClosedList.Clear();
                

                //add only the starting node

                //reset path node ID
                _PathNodeID = -1;
                //add start node:
                _PathNodeID += 1;
                _StartNode.PathID = _PathNodeID;
                _StartNode.IsParent = true;

                //add to the open list first
                OpenList.Add(_StartNode);

                _SearchRestartNeeded = false;



            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }

        /// <summary>
        /// end path finding
        /// clear everything and forget
        /// </summary>
        public static void EndPathFinding()
        {
            try
            {
                //instantiate lists
                //Nodes = null;
                if (WorldManager.Nodes != null)
                {
                    for (int i = 0; i < WorldManager.Nodes.Count; i++)
                    {
                        WorldManager.Nodes[i].ResetNode();
                    }
                }

                OpenList = null;
                ClosedList = null;
                _EndPoint = new Vector2(-1, -1);
                _StartNode = null;
                //NumOfNodesVert = -1;
                //NumOfNodesHor = -1;
                _PathNodeID = -1;


            }
            catch (Exception ex)
            {
                Util.ErrorLogging.LogError(ex);
                return;
            }
        }





        #endregion


    }
}
